Dukolora grafeo

La artikolo estas parto de serio pri grafeoteorio.

Plej gravaj terminoj grafeo arbo subgrafeo ciklo kliko grado de vertico grado de grafeo Elektitaj klasoj de grafeoj plena grafeo plena dukolora grafeo kohera grafeo arbo grafeo dudividebla Fenda grafeo regula grafeo grafeo de Euler grafeo de Hamilton grafeo senrelifa pli... Grafeaj algoritmoj A* Bellman-Ford Dijkstry Fleury Floyd-Warshall Johnson Kruskal Prim traserĉado de grafeo – en larĝeco – en profundo plej proksima najbaro Problemoj prezentataj kiel grafeaj problemo de vojaĝisto problemo de ĉina leteristo problemo de marŝrutigado problemo de kunigado de geedzoj Aliaj kodo de Gray diagramo de Hasse kodo de Prüfer Reprezentado de grafeo Glosaro de grafeoteorio

vidi • diskuti • redakti

En grafeoteorio, dukolora grafeo (aŭ duparta grafeo) estas grafeo kies verticojn oni povas dividi en du disajn arojn ${\displaystyle U}$ kaj ${\displaystyle V}$, en kiu ĉiu eĝo ligas verticon en ${\displaystyle U}$ al vertico en ${\displaystyle V}$. Verticaro ${\displaystyle U}$ kaj ${\displaystyle V}$ ofte nomiĝas la partoj de la grafeo. Ekvivalente, dukolora grafeo estas grafeo sen nepara ciklo.^[1][2]

La du partojn ${\displaystyle U}$, ${\displaystyle V}$ oni povas pripensi kiel kolorado de la grafeo per du koloroj: ekzemple verticoj en ${\displaystyle U}$ estu bluaj, kaj verticoj en ${\displaystyle V}$ verdaj. Do la randoj de ĉiu eĝo havas malsamajn kolorojn.^[3][4] Kontraste, ĉi tia kolorado ne eblas en ne-dukolora grafeo, ekzemple unu triangulo.

Oni ofte skribas ${\displaystyle G=(U,V,E)}$ por signifi dukolora grafeo kun partoj ${\displaystyle U}$ kun ${\displaystyle V}$, kaj ${\displaystyle E}$ signas la eĝaro. Se dukolora grafeo ne estas konekteca, ĝi eble havas plurajn dukoloradojn;^[5] tiel,  ${\displaystyle (U,V,E)}$ povas signi unu el la dukoloradoj utila por la nuna problemo. Se ${\displaystyle |U|=|V|}$, t.e. la du partoj enhavas same da elementoj, ${\displaystyle G}$ nomiĝas ekvilibra dukolora grafeo.^[3] Se ĉiuj verticoj en ambaŭ partoj havas saman gradon, ${\displaystyle G}$ nomiĝas duregula.

1. ↑ Diestel, Reinard. (2005) Graph Theory, Grad. Texts in Math. Springer. ISBN 978-3-642-14278-9.
2. ↑ Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, (ISBN 9780521593458) .
3. ↑ ^{3,0 3,1} Asratian, Denley & Häggkvist (1998), p. 7.
4. ↑ . ISBN 9780840049421.
5. ↑ . ISBN 9781584888000..